An array is a basic data structure used for data aggregation and the like. The array has a storage area (main area) in which values as data are stored in association with indices. When read and write are executed on indices 0≤i<N and read is executed on a certain index i, the array returns the last value written to the main area at the index i. Normal initialization of the array involves an initialization process in which an initial value is written to the main area at all the indices. This leads to the need for an initialization time proportional to an array size N.
On the other hand, in a data structure referred to as an initializable array, all the indices 0≤i<N are set to the initial value when, in addition to the above-described read and write, initialization is performed. The initializable array is configured to specially support the initialization and performs an initialization process in a given time regardless of the array size N. For example, a technique for a word random-access machine (RAM) model is known. In the technique, when initialization “initialize (x)” is invoked, an initial value x is stored. Management information is stored that indicates whether the write has been executed on each index i. When the read is invoked for an index on which no write has been executed, the initial value x stored during the initialization is returned.
Such a data structure for the initializable array is utilized, for example, when an application program that needs to operate in real time needs to execute the initialization process in a fixed time independently of the size N of the array. The data structure for the array is described in Japanese Laid-open Patent Publication Nos. H05-158783, 2002-207634, 2004-30353, and Japanese National Publication of International Patent Application No. 2009-521049, and A. Aho, J. Hoperoft, and J. Ullman, “The Design and Analysis of Computer Algorithms” Addison-Wesley, 1974, and 2 G. Navarro, “Dynamic dictionaries in constant worst-case time” Technical Report TR/DCC-2007-11, University of Chile, Department of Computer Science, October 2007.